1. Field of the Invention
The present invention relates to logic circuits, and more particularly to implementations of high fan-in logic functions in a dynamic logic circuit.
2. Description of the Related Art
Dynamic circuits are frequently used to implement logic functions in present day pipelined systems because of speed demands. FIG. 1 is a schematic diagram of an AND gate 100 representing an AND logic function and an exemplary dynamic circuit 102 for implementing the AND gate 100. The dynamic circuit 102 and the AND gate 100 each are shown having “N” inputs, individually shown as D1, D2, . . . , DN, and a single output referred to as “Q”. The dynamic circuit 102 includes a P-channel header device P0, an N-channel footer device N0, a logic function for evaluation implemented by a logic circuit 104, an output buffer or inverter/driver U1, and a storage or keeper circuit 106. In the embodiment shown, the keeper circuit 106 is implemented with inverter devices U2 and U3, in which the output of U2 is coupled to the input of U3 and vice-versa.
The dynamic circuit 102 establishes the Q signal at the output of the inverter/driver U1 on a rising edge of an associated clock signal “CLK”. The dynamic nature of a dynamic logic circuit is controlled by the CLK signal in which the circuit is in a set-up or pre-charged state while CLK is negated low and in an evaluation state when CLK is asserted high. The CLK signal is provided to respective gates of the header device P0 and the footer device N0. The header device P0 has a source coupled to a source voltage “VDD” and a drain coupled to an evaluation node referred to as “HI”. It is noted that a node and its corresponding signal are referred to herein by the same name, e.g., node HI carries the HI signal. The footer device N0 has a source coupled to a common reference voltage “GND” and a drain coupled to a reference node referred to as “LO”. The logic circuit 104 is coupled between the HI and LO nodes. In the embodiment shown, the logic circuit 104 is implemented in N-channel logic, or “N-logic”, using a number “N” of N-channel devices N1-NN coupled in series between the HI and LO nodes. In particular, a first N-channel device N1 has its drain coupled to HI and its source coupled to the drain of the next N-channel device N2, and so on down to a last N-channel device NN having its source coupled to LO. Each of the N inputs D1-DN is provided to a respective one of the N-channel devices N1-NN. The HI node is further coupled to the inputs of the inverter devices U1 and U2 and to the output of the inverter device U3.
In operation, while the CLK signal is low, the HI node is pre-charged to a logic high level by the header device P0, the Q signal is pulled low via the inverter/driver U1 and the input signals D1-DN setup for evaluation of the logic function. When the CLK signal goes high, based on the state of the inputs D1-DN, the logic function of the logic circuit 104 either evaluates or “fails” to evaluate. If the logic circuit 104 evaluates, in which all of the input signals D1-DN are asserted high turning on all of the N-channel devices N1-NN, the logic circuit 104 drives the HI node to a logic low level via the activated footer device N0 and the Q output signal is driven to a logic high level. Once the HI node is driven low, it stays low until the CLK signal is driven low again. If the logic circuit 104 fails to evaluate, the keeper circuit 106 maintains the HI node at a high logic level, so that the Q signal remains low. Hence, the Q signal is low when the CLK signal is low, and the Q signal can be driven high by the logic circuit 104 while the CLK signal is high if the logic function is TRUE.
The logic function implemented by the logic circuit 104 is a multiple-input AND function. To evaluate, all of the inputs D1-DN must be at a logic high level while the CLK signal is high. AND logic functions are typically implemented in N-logic by connecting N-channel devices in series as shown within the logic circuit 104. Such series or “stack” connections of N-channel devices causes problems in a dynamic circuit for at least two reasons. First, the length of the evaluation path between the HI and LO nodes is a function the number of devices in the evaluation path of the logic circuit which is, in turn, a function of the fan-in (i.e., the number of inputs to be ANDed together). Long evaluation paths required to evaluate a relatively large number of input signals requires a longer time to evaluate, thus slowing down the overall circuit. Second, because N-channel devices are employed to implement the evaluation function, devices higher in the stack are subject to device body effects. Device body effects cause the device thresholds to change due to stacking, thus providing the potential for instability of the circuit.
To address the problems associated with the length of the evaluation path, logic designers usually limit the size of each stack to no more than about four levels. In general, evaluation paths with two levels is a desirable configuration. The solution of limiting the evaluation path may be accomplished by either implementing the inverse function using OR terms or decomposing high fan-in AND functions into a staged series of low fan-in AND functions.
Implementing the inverse of an AND function involves converting the series AND path to a parallel OR path with parallel OR terms. The solution of inverting to the OR logic function suffices for simple functions in which an inverted output is acceptable. The inversion solution is unworkable under complex logic conditions, however, since converting AND terms to OR terms in a first stage of a logic operation necessitates that OR terms in a following stage be converted to AND terms. Consequently, inversion merely relegates the N-stack problem to the following logic stage.
FIG. 2 is a schematic diagram of a 16-input AND gate 200 and an exemplary logic circuit 202 for implementing the AND gate 200 illustrating a conventional decomposition solution. The AND gate 200 has 16 input signals, individually shown as A1-A16, and an output signal Q, and is considered a high fan-in AND function. The single AND gate 200 is implemented by a series of four low fan-in stages 204, 206, 208 and 210, each stage including one or more 2-input AND gates. In particular, the first stage 204 includes eight AND gates, each receiving a respective pair of the input signals A1-A16. The second stage 206 includes four AND gates, each having a pair of inputs coupled to respective outputs of pairs of AND gates of the first stage 204. The third stage 208 includes two AND gates, each having a pair of inputs coupled to respective outputs of pairs of AND gates of the second stage 206. The fourth and final stage 210 includes a single AND gate having a pair of inputs coupled to respective outputs of the two AND gates of the third stage 208.
It is noted that each AND function of the logic circuit 202 has only two inputs so that the respective evaluation paths are decomposed to the desirable configuration with low fan-in. Decomposing a high fan-in AND function into staged low fan-in AND operations is undesirable, nevertheless, because each additional series-coupled stage of the decomposed function adds delay to the overall circuit. The number of AND gates may be decreased by increasing the fan-in per AND gate, such as down to only five 4-input AND gates, each with the maximum number of recommended fan-ins of four. This latter solution still suffers from delay, however, since each AND function has a relatively large fan-in and two stages are still required.